#include "DynamicArray.h"
#include <iostream>
#include <cmath>
namespace DArray
{
    DynamicArray::DynamicArray(size_t capacity) : size(0), capacity(capacity)
    {
        array = new ElementType[capacity];
    }

    DynamicArray::DynamicArray(const DynamicArray &a)
    {
        size = a.size;
        capacity = a.capacity;
        array = new ElementType[capacity];
        for (size_t i = 0; i < size; i++)
        {
            array[i] = a.array[i];
        }
    }

    DynamicArray &DynamicArray::operator=(const DynamicArray &a)
    {
        delete[] array;

        size = a.size;
        capacity = a.capacity;
        array = new ElementType[capacity];
        for (size_t i = 0; i < size; i++)
        {
            array[i] = a.array[i];
        }
        return *this;
    }

    DynamicArray::~DynamicArray()
    {
        delete[] array;
    }

    size_t DynamicArray::Size()
    {
        return size;
    }

    // 接口可扩大扩小
    void DynamicArray::ReSize(size_t capacity)
    {
        this->capacity = capacity;
        this->size = (size > capacity) ? capacity : size;
        ElementType *newP = new ElementType[capacity];
        for (size_t i = 0; i < size; i++)
        {
            newP[i] = array[i];
        }
        delete[] array;
        array = newP;
    }

    // 尾插
    void DynamicArray::InsertTail(const ElementType &element)
    {
        if (size >= capacity)
            ReSize(2 * capacity);

        array[size++] = element; // O(1)
    }

    // 头插
    void DynamicArray::InsertHead(const ElementType &element)
    {
        if (size >= capacity)
            ReSize(2 * capacity);

        for (size_t i = size; i > 0; i--) // O(n)
        {
            array[i] = array[i - 1];
        }
        array[0] = element;
        size++;
    }

    // 中间插入
    void DynamicArray::InsertByIndex(int index, const ElementType &element)
    {
        // 非法位置排除
        if (index < 0 || index > size)
        {
            return;
        }
        if (size >= capacity)
            ReSize(2 * capacity);

        for (size_t i = size; i > index; i--) // O(n)
        {
            array[i] = array[i - 1];
        }
        array[index] = element;
        size++;
    }

    // 按位删除
    void DynamicArray::RemoveByIndex(int index)
    {
        // 非法位置排除
        if (index < 0 || index >= size)
        {
            return;
        }
        for (size_t i = index; i < size - 1; i++) // O(n)
        {
            array[i] = array[i + 1];
        }
        size--;
    }

    // 按值删除
    void DynamicArray::RemoveByElement(const ElementType &element, bool (*equalPtr)(ElementType, ElementType))
    {

        for (size_t i = 0; i < size; i++) // O(n^2)
        {
            if (equalPtr(array[i], element) == true)
            {
                RemoveByIndex(i);
                i--;
            }
        }
    }

    // 按位置查
    ElementType *DynamicArray::FindByIndex(int index)
    {
        if (index < 0 || index >= size)
        {
            return nullptr;
        }
        return &array[index]; // O(1)
    }

    ElementType &DynamicArray::operator[](int index)
    {
        return array[index];
    }

    // 按值查找
    DynamicArray DynamicArray::FindByElement(const ElementType &element, bool (*equalPtr)(ElementType, ElementType))
    {
        DynamicArray result;
        for (int i = 0; i < size; i++) // O(n)
        {
            if (equalPtr(array[i], element) == true)
            {
                result.InsertTail(array[i]);
            }
        }
        return result;
    }

    // 按位置进行修改
    void DynamicArray::UpdataByIndex(int index, const ElementType &element)
    {
        if (index < 0 || index >= size)
            return;
        array[index] = element; // O(1)
    }

    // 按值修改
    void DynamicArray::UpdataByElement(const ElementType &oldValue, const ElementType &newValue, bool (*equalPtr)(ElementType, ElementType))
    {
        for (int i = 0; i < size; i++)
        {
            if (equalPtr(array[i], oldValue) == true)
            {
                array[i] = newValue;
            }
        }
    }

    // 排序
    void DynamicArray::Sort(bool (*equalPtr)(ElementType, ElementType))
    {
        FastSort(0, size - 1, 0, 2 * log2(size), equalPtr);
    }

    // 去重算法
    void DynamicArray::Duplicate(bool (*equalPtr)(ElementType, ElementType))
    {
        for (int i = 1; i < size; i++)
        {
            if (equalPtr(array[i], array[i - 1]) == true)
            {
                RemoveByIndex(i);
                i--;
            }
        }
    }

    // //合并两个已经有序的数列(归并算法)
    DynamicArray DynamicArray::Merge(const DynamicArray &a, bool (*equalPtr)(ElementType, ElementType))
    {
        size_t first = 0;  // 当前数组
        size_t second = 0; // 传入的数组
        DynamicArray result;
        // 遍历两个数组都没有到结尾
        while (first < this->size && second < a.size)
        {
            if (equalPtr(this->array[first], a.array[second]) == true)
            {
                result.InsertTail(array[first++]);
            }
            else
            {
                result.InsertTail(a.array[second++]);
            }
        }
        while (first < this->size)
        {
            result.InsertTail(array[first++]);
        }
        while (second < a.size)
        {
            result.InsertTail(a.array[second++]);
        }
        return result;
    }

    // 找交集
    DynamicArray DynamicArray::FndInterSctn(const DynamicArray &a, bool (*equalPtr)(ElementType, ElementType), bool (*equalPtr1)(ElementType, ElementType))
    {
        DynamicArray result;
        // for(int i = 0; i < size; i++)
        // {
        //     for(int j = 0; j < size; j++)
        //     {                                O(n^2)
        //         if(array[i] == a.array[j])
        //         {
        //             result.InsertTail(array[i]);
        //         }
        //     }
        // }
        // result.Sort();
        // result.Duplicate();

        int first = 0;
        int second = 0;
        while (first < size && second < a.size)
        {
            if (equalPtr)
            {
                result.InsertTail(array[first]);
                first++;
                second++;
            }
            else if (equalPtr1)
            {
                second++;
            }
            else
            {
                first++;
            }
        }
        return result;
    }

    // 找并集
    DynamicArray DynamicArray::FindUnionSet(const DynamicArray &a, bool (*equalPtr)(ElementType, ElementType), bool (*equalPtr1)(ElementType, ElementType))
    {
        DynamicArray result;
        int first = 0;
        int second = 0;
        while (first < size && second < a.size)
        {
            if (equalPtr)
            {
                result.InsertTail(array[first++]);
                second++;
            }
            else if (equalPtr1)
            {
                result.InsertTail(array[second++]);
            }
            else
            {
                result.InsertTail(array[first++]);
            }
        }
        // 有序算法 O(n)
        while (first < this->size)
        {
            result.InsertTail(array[first++]);
        }
        while (second < a.size)
        {
            result.InsertTail(a.array[second++]);
        }

        return result;
    }

    // 插入排序
    void DynamicArray::InsertSort(size_t start, size_t end, bool (*equalPtr)(ElementType, ElementType))
    {

        for (size_t i = start; i <= end; i++)
        {
            size_t j = i;
            ElementType temp = array[i];
            for (; j > start; j--)
            {
                if (equalPtr(array[j - 1], temp) == true)
                {
                    array[j] = array[j - 1];
                }
                else
                {
                    break;
                }
            }
            array[j] = temp;
        }
    }

    // 找补集
    DynamicArray DynamicArray::FindDifference(const DynamicArray &a, bool (*equalPtr)(ElementType, ElementType), bool (*equalPtr1)(ElementType, ElementType))
    {
        DynamicArray result;
        int first = 0;
        int second = 0;
        while (first < size && second < a.size)
        {
            if (equalPtr)
            {
                // result.InsertTail(array[first++]);
                first++;
                second++;
            }
            else if (equalPtr1)
            {
                result.InsertTail(array[second++]);
            }
            else
            {
                result.InsertTail(array[first++]);
            }
        }
        // 有序算法 O(n)
        while (first < this->size)
        {
            result.InsertTail(array[first++]);
        }
        while (second < a.size)
        {
            result.InsertTail(a.array[second++]);
        }

        return result;
    }
    // 判断两个数列是否相等
    bool DynamicArray::operator==(const DynamicArray &a)
    {
        if (size != a.size)
            return false;
        int first = 0;
        int second = 0;
        while (first < size && second < a.size)
        {
            if (array[first++] != a.array[second++]) // O(n)
                return false;
        }
        return true;
    }

    // 二分查找
    size_t DynamicArray::BinarySearch(const ElementType &element, bool (*equalPtr)(ElementType, ElementType))
    {
        size_t left = 0;
        size_t right = size - 1;
        while (left <= size)
        {
            size_t mid = left + (right - left) / 2;
            if (equalPtr(array[mid], element))
            {
                if (mid == 0)
                    return ULLONG_MAX;
                right = mid - 1;
            }
            else if (equalPtr(element, array[mid]))
                left = mid + 1;
            else
                return mid;
        }

        return ULLONG_MAX;
    }

    // 查找一个数列是不是子数列
    bool DynamicArray::IsChild(const DynamicArray &a)
    {
        // for(int i = 0; i < a.size; i++)
        // {
        //     if(FindByElement(a.array[i]).size == 0)  //O(n)
        //     {
        //         return false;
        //     }
        // }

        // return true;
        int j = 0;
        for (int i = 0; i < size; i++)
        {
            if (array[i] == a.array[j]) // O(n)
            {
                j++;
            }
        }
        return j == a.size;
    }

    // 查找连续子序列
    bool DynamicArray::IsCntnsChilid(const DynamicArray &a) // O(n^2)
    {
        for (int i = 0; i <= size - a.size; i++)
        {
            if (subsequence(i, a.size) == a)
            {
                return true;
            }
        }
        return false;
    }
    // 获取子序列
    DynamicArray DynamicArray::subsequence(int index, size_t size)
    {
        if (index < 0 || index + size > this->size)
            return DynamicArray();
        DynamicArray result;
        for (int i = index; i < index + size; i++)
        {
            result.InsertTail(array[i]);
        }
        return result;
    }
    // 输出
    void DynamicArray::show(void (*PrintPtr)(ElementType))
    {
        for (int i = 0; i < size; i++)
        {
            PrintPtr(array[i]);
        }
    }

    void DynamicArray::FastSort(size_t start, size_t end, size_t deepth, size_t MaxDeepth, bool (*equalPtr)(ElementType, ElementType))
    {

        if (start >= end)
            return;
        // 改用插入排序
        if (deepth > MaxDeepth)
        {
            InsertSort(start, end, equalPtr);
        }
        // 没超过最大深度，继续快排分组
        else
        {
            size_t par = Partition(start, end, equalPtr);
            if (par != 0)
                FastSort(start, par - 1, deepth + 1, MaxDeepth, equalPtr);
            FastSort(par + 1, end, deepth + 1, MaxDeepth, equalPtr);
        }
    }

    // 分组
    size_t DynamicArray::Partition(size_t start, size_t end, bool (*equalPtr)(ElementType, ElementType))
    {
        size_t left = start;
        size_t right = end;
        ElementType temp = array[left];
        while (left < right)
        {
            while (right > left && equalPtr(array[right], temp))
                right--;
            if (left < right)
                array[left++] = array[right];
            while (left < right && equalPtr(temp, array[left]))
                left++;
            if (left < right)
                array[right--] = array[left];
        }
        array[left] = temp;
        return left;
    }
}
